#q111
# 给定一个二叉树，找出其最小深度。
#
# 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
#
# 说明：叶子节点是指没有子节点的节点。
from typing import *
import collections
class TreeNode:
    def __init__(self,data):
        self.data = data
        self.right =None
        self.left = None
    def insert(self,new_data):
        if new_data < self.data:
            if self.left is None:
                self.left = TreeNode(new_data)
            else:
                self.left.insert(new_data)
        else:
            if self.right is None:
                self.right = TreeNode(new_data)
            else:
                self.right.insert(new_data)

class Solution1:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0

        if not root.left and not root.right:
            return 1

        min_depth = 10 ** 9
        if root.left:
            min_depth = min(self.minDepth(root.left), min_depth)
        if root.right:
            min_depth = min(self.minDepth(root.right), min_depth)

        return min_depth + 1

class Solution2:
    def minDepth(self,root:TreeNode) -> int:
        q = [root]
        depth =0
        while q:
            cur = q.pop()
            if (cur.left is None) and (cur.right is None):
                return depth
            elif cur.left is not None:
                q.append(cur.left)
            elif cur.right is not None:
                q.append(cur.right)
            depth +=1
        return depth



if __name__=="__main__":
    root = TreeNode(12)
    root.insert(6)
    root.insert(14)
    root.insert(3)
    s = Solution2()
    print(s.minDepth(root))